package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"
)

func main1() {
	var a, b int
	for {
		_, err := fmt.Scan(&a, &b)
		if err == io.EOF {
			break
		}
		fmt.Println(a + b)
	}
}

func main2() {
	var n, a, b int
	fmt.Scan(&n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a, &b)
		fmt.Println(a + b)
	}
}

func main3() {

	sc := bufio.NewScanner(os.Stdin)
	for sc.Scan() {
		strs := strings.Split(sc.Text(), " ")
		one, _ := strconv.Atoi(strs[0])
		if one == 0 {
			return
		}
		sum := 0
		for _, str := range strs {
			num, _ := strconv.Atoi(str)
			sum += num
		}
		fmt.Println(sum)
	}
}

func main4() {
	sc := bufio.NewScanner(os.Stdin)
	for sc.Scan() {
		fmt.Printf("sc.Text(): %v\n", sc.Text())
	}
}

func main5() {
	var N, E int
	fmt.Scan(&N, &E)
	launches := make([]int, N)

	for i := 0; i < N; i++ {
		launches[i] = 2000
	}
	for i := 0; i < E; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		launches[b] = a
	}

	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			var innerDis int = int(math.Abs(float64(i - j)))
			var outerDis int = N - innerDis
			var dis int = min(innerDis, outerDis)
			launches[j] = min(launches[j], launches[i]+dis)
		}
	}
	for i := 0; i < N; i++ {
		fmt.Printf("launches[i]: %v\n", launches[i])

	}
	var maxTime int = 0
	ans := []string{}
	for i := 0; i < len(launches); i++ {
		if launches[i] < maxTime {
			continue
		}
		if launches[i] > maxTime {
			maxTime = launches[i]
			ans = ans[:0]
		}
		ans = append(ans, strconv.Itoa(i+1))

	}
	fmt.Println(len(ans))
	fmt.Println(strings.Join(ans, ","))
}

func main6() {
	var n int
	fmt.Scan(&n)
	childToParent := make(map[int]int)
	parentToChildren := make(map[int][]int)
	salaries := make(map[int]int64, n)
	ids := make(map[int]int)
	for i := 0; i < n; i++ {
		var a, b int
		var c int64
		fmt.Scan(&a, &b, &c)
		salaries[a] = c
		childToParent[a] = b
		var tmp []int
		if v, f := parentToChildren[b]; f {
			tmp = v
			tmp = append(tmp, a)
		} else {
			tmp = append(tmp, a)
		}
		parentToChildren[b] = tmp

		ids[a] = 0
		ids[b] = 0
	}

	for id, _ := range ids {
		if _, f := childToParent[id]; !f {
			salaries[id] = 0
			calcTotalIncome(id, parentToChildren, salaries)
			fmt.Println(id, salaries[id])
		}
	}
}

func calcTotalIncome(parentId int, parentToChildren map[int][]int, salariesmap map[int]int64) {
	childlist := parentToChildren[parentId]
	for _, id := range childlist {
		calcTotalIncome(id, parentToChildren, salariesmap)
		additionSalary := salariesmap[id] / 100 * 15
		salariesmap[parentId] = salariesmap[parentId] + additionSalary
	}
}

func main7() {
	var n, m int
	fmt.Scan(&n, &m)

	var message [][3]int = make([][3]int, m)

	for i := 0; i < m; i++ {
		fmt.Scan(&message[i][0], &message[i][1], &message[i][2])
	}

	if n < 1 || n >= 100000 || m < 1 || m >= 100000 {
		fmt.Println("NULL")
		return
	}

	var parents []int = make([]int, n+1)
	for i := 1; i < n; i++ {
		parents[i] = i
	}

	var find func(x int) int
	find = func(x int) int {
		if x != parents[x] {
			parents[x] = find(parents[x])
		}
		return parents[x]
	}
	for i := 0; i < m; i++ {
		if message[i][0] < 1 || message[i][0] > n || message[i][1] < 1 || message[i][1] > n || message[i][2] < 0 || message[i][2] > 1 {
			fmt.Println("da pian zi")
			continue
		} else if message[i][2] == 0 {
			root1, root2 := find(message[i][0]), find(message[i][1])
			if root1 != root2 {
				parents[root1] = root2
			}
		} else {
			root1, root2 := find(message[i][0]), find(message[i][1])
			if root1 == root2 {
				fmt.Println("We are a team")
			} else {
				fmt.Println("We are not a team")
			}
		}
	}
}

func main8() {
	var n, m int
	fmt.Scan(&n)
	fmt.Scan(&m)

	if n < 3 || n > 7 {
		fmt.Println(-1)
		return
	}
	start := int(math.Pow(10, float64(n-1)))
	end := int(math.Pow(10, float64(n)))
	ans := make([]int, 0)
	for i := start; i < end; i++ {
		if isNarcissus(i, n) {
			ans = append(ans, i)
		}
	}
	fmt.Println(ans[0])

}

func isNarcissus(x, n int) bool {
	sum, tmp := 0, x
	for tmp > 0 {
		sum += int(math.Pow(float64(tmp%10), float64(n)))
		tmp = tmp / 10
	}
	return x == sum
}

func main9() {
	var m, n int
	fmt.Scan(&m, &n)
	var matrix [][]int = make([][]int, m, n)

	for i := 0; i < m; i++ {
		var row []int = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&row[j])
		}
		matrix[i] = row
	}
	cnt := dfs(matrix, 0, 0)
	fmt.Println(m*n - cnt)

}

func dfs(matrix [][]int, x, y int) int {
	count := 1
	matrix[x][y] = 1
	directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for i := 0; i < len(directions); i++ {
		tmpx, tmpy := x+directions[i][0], y+directions[i][1]
		if isValid(matrix, tmpx, tmpy) {
			count += dfs(matrix, tmpx, tmpy)
		}
	}
	return count
}

func isValid(matrix [][]int, x, y int) bool {
	return x >= 0 && x < len(matrix) && y >= 0 && y < len(matrix[0]) && matrix[x][y] == 0
}
